一、GNN [2009]

《The Graph Neural Network Model》

1. 数据可以在许多应用领域中自然地用图结构（graph structure）来表达，包括蛋白质组织学（proteomics）、图像分析、场景描述、软件工程、自然语言处理。最简单的图结构包括单节点（single node）、序列（sequence）。但是在一些应用中，信息被组织成更复杂的图结构，如树、无环图、带环图。传统上，数据关系探索一直是归纳式逻辑编程（inductive logic programming）的社区中许多研究的主题。最近，数据关系探索（data relationships exploitation）这个研究主题已经朝着不同的方向发展，这也是因为统计（statistics）和神经网络中的相关概念在这些领域中的应用。

   在机器学习中，结构化数据通常与（有监督的或者无监督的）learning 的目标相关联，例如一个函数 $\tau$$\tau$ 将一个图 $\mathbf{G}$$\mathbf G$ 和该图的一个节点 $n$$n$ 映射为一个实数向量 $\tau (\mathbf{G},v)\in {\mathbb{R}}^m$$\tau(\mathbf G,v) \in \mathbb R^m$ ，其中 $m$$m$ 为向量的维度。在本文中，图领域的应用（application）通常可以分为两大类，分别称作 graph-focused 应用、node-focused 应用 。

   • 在 graph-focused 应用中，函数 $\tau$$\tau$ 独立于节点 $n$$n$ ，并且在图结构的数据集上实现分类器或回归器。

     此时每个图具有一个 representation，并且每个图具有一个 target。

     例如，可以用一个图 $\mathbf{G}$$\mathbf G$ 来建模一种化合物，图的节点代表原子（或者化学基团）、边代表将原子连接起来的化学键。如下图所示。这个函数 $\tau (\mathbf{G})$$\tau(\mathbf G)$ 可用于估计化合物引起某种疾病的概率。

     

     在下图中，图片由区域邻接图（region adjacency graph）来表达，其中节点表示均匀图片强度的区域，边代表这些区域的邻接关系。在这种情况下，可以根据图片的内容通过 $\tau (\mathbf{G})$$\tau(\mathbf G)$ 将图片分为不同的类别，如城堡、汽车、人等等。

     

   • 在 node-focused 应用中，函数 $\tau$$\tau$ 取决于节点 $n$$n$ ，因此分类（或回归）取决于每个节点的属性。

     此时每个节点具有一个 representation，并且每个节点具有一个 target 。

     例如目标检测 application 包括检查图片中是否包含给定的对象，如果是，则定位给定对象的位置。这个问题可以通过一个函数 $\tau$$\tau$ 来解决，该函数根据区域邻接图是否属于目标对象，从而对区域邻接图进行节点分类。例如，下图中的黑色节点，如果对应于城堡则 $\tau$$\tau$ 输出为 1、否则 $\tau$$\tau$ 输出为 0 。

     

     另一个例子来自于网页分类。web 可以通过一个图来表达，其中节点代表网页，边代表网页之间的超链接，如下图所示。可以利用 web connectivity 以及网页内容来实现多种目的（purposes），如页面的主题分类。

     

   传统的机器学习 application 通过使用预处理（ preprocessing ）阶段来处理图结构化数据（graph structured data），该阶段将图结构化信息映射到更简单的 representation，如实值向量。换句话讲，预处理步骤首先将图结构化数据 "squash" 为实数向量，然后使用 list-based 数据处理技术来处理 preprocessed的数据。然而，在预处理阶段，一些重要的信息（如每个节点的拓扑依赖性 topological dependency）可能会丢失，并且最终结果可能以不可预知的方式（unpredictable manner ）取决于预处理算法的细节。

   最近，有各种方法试图在预处理阶段尽可能地保留数据的图结构特性，其思想是：使用图节点之间的拓扑关系对底层的图结构化数据进行编码，以便在数据正式处理步骤（即预处理步骤之后的模型处理阶段）中融合图结构化信息。这组技术包括 recursive neural network: RNN、马尔科夫链（Markov chain: MC），并且通常可以同时应用于 graph-focused 问题和 node-focused 问题。论文 《The Graph Neural Network Model》提出的方法扩展了这两种方法（即 RNN 和马尔科夫链），因为该方法可以直接处理图结构化信息。

   • 现有的 RNN 是以有向无环图（directed acyclic graph）作为输入的神经网络模型。该方法估计函数 ${\phi }_{\mathbf{w}}$$\varphi_{\mathbf w}$ 的参数 $\mathbf{w}$$\mathbf w$，其中函数 ${\phi }_{\mathbf{w}}$$\varphi_{\mathbf w}$ 将图映射到实值向量。该方法也可以用于 node-focused application 中，此时，图必须经过预处理阶段。类似地，采用预处理阶段之后，我们可以处理某些类型的带环图。RNN 已被应用于多个问题，包括逻辑术语分类 （logical term classification）、化合物分类、logo 识别、网页评分、人脸定位 （face localization）。

     RNN 也与支持向量机有关，其中支持向量机采用特殊的 kernel 对图结构化数据进行操作，其中：

     • diffusion kernel 是基于热扩散方程（heat diffusion equation）。

     • 《Marginalized kernels between labeled graphs》和 《Extensions of marginalized graph kernels》 中提出的 kernel 利用了图随机游走生成的向量。

     • 《Convolution kernels for natural language》、《Kernels for structured natural language data》、《Convolution kernels with feature selection for natural language processing tasks》 中设计的 kernel 使用了一种计算两棵树的公共子结构数量的方法。

     事实上，类似于支持向量机方法，RNN 自动将输入的图编码为内部 representation。然而，在 RNN 中内部编码是模型自动学到的，而在支持向量机中内部编码是由用户手动设计的。

   • 另一方面，马尔科夫链模型可以建模事件之间的因果关系，其中因果关系由图来表达。最近，针对特定种类马尔科夫链模型的随机游走理论已成功应用于网页排名（ranking）算法的实现。互联网搜索引擎使用排名算法来衡量网页的相对重要性。这类度量值通常与其它页面特征一起被搜索引擎所利用，从而对用户 query 返回的 URL 进行排序。人们已经进行了一些尝试来扩展这些具有学习能力的模型，以便可以从训练样本中学习模型参数。这些模型能够泛化结果从而对集合中的所有网页进行评分。更一般地，人们已经提出了几种其它统计方法，这些方法假设数据集由模式 （pattern）、以及模式之间的关系 （relationship） 组成。这些技术包括：随机场（random field）、贝叶斯网络、统计关系学习、transductive learning、用于图处理的半监督方法。

   在论文 《The Graph Neural Network Model》 中，作者提出了一种有监督的神经网络模型，该模型同时适用于 graph-focused application 和 node-focused application。该模型将这两个现有模型（即 RNN 和马尔科夫链）统一到一个通用框架中。论文将这种新颖的神经网络模型称作图神经网络 （graph neural network: GNN）。论文将证明 GNN 是 RNN 和随机游走模型的扩展，并且保留了它们的特性 （characteristics）。

   • GNN 模型扩展了 RNN，因为 GNN 可以处理更通用的图，包括带环图、有向图、无向图，并且无需任何预处理步骤即可处理 node-focused application 。

   • GNN 方法通过引入 learning 算法、以及扩大可建模过程的种类从而扩展了随机游走理论。

   GNN 基于信息扩散机制 （information diffusion mechanism）。图由一组单元（unit ）来处理，每个单元对应于图上的一个节点，这些节点根据图的连通性进行链接。这些单元更新它们的状态并交换信息，直到它们到达稳定的平衡（stable equilibrium）。然后，基于单元的状态（unit state ）计算每个节点的输出。扩散机制是受约束（constrained）的，从而确保始终存在唯一的稳定平衡。

   这种实现机制已经在细胞神经网络、Hopfield 神经网络中使用。在那些神经网络模型中，连通性是根据预定义的图来指定的，网络连接本质上是循环 （recurrent）的，神经元状态是通过松弛（relaxation）到平衡点（equilibrium point）来计算的。GNN 与那些神经网络不同之处在于：GNN 可以处理更加通用的图，并且采用更通用的扩散机制。

   在论文 《The Graph Neural Network Model》 中，作者将介绍一种学习算法，该算法在一组给定的训练样本上估计 GNN 模型的参数。此外，参数估计算法的计算代价需要被考虑。还值得一提的是，《Computation capabilities of graph neural networks》 已经证明了 GNN 展示出一种普遍的逼近特性，并且在不严厉的条件下，GNN 可以逼近图上大多数实际有用的函数 $\phi$$\varphi$ 。

1.1 模型

1. 定义图 $\mathbf{G}=(\mathbf{N},\mathbf{E})$$\mathbf G=(\mathbf N,\mathbf E)$，其中 $\mathbf{N}$$\mathbf N$ 为节点集合、$\mathbf{E}$$\mathbf E$ 为边集合。边可以为有向边，也可以为无向边。对于节点 $n\in \mathbf{N}$$n\in \mathbf N$ ，定义 $\text{ne}[n]$$\text{ne}[n]$ 为其邻接节点集合（即，邻域），定义 $\text{co}[n]$$\text{co}[n]$ 为包含节点 $n$$n$ 的边的集合。

   节点和边可能含有额外的信息，这些信息统称为标签信息（它和监督学习中的 label 不是一个概念），并以实值向量的形式来表示。

   • 定义节点 $n$$n$ 的标签为 ${\overrightarrow{l}}_n\in {\mathbb{R}}^{d_N}$$\vec l_n\in \mathbb R^{d_N}$ ，定义边 $(n_1,n_2)$$(n_1,n_2)$ 的标签为 ${\overrightarrow{l}}_{n_1,n_2}\in {\mathbb{R}}^{d_E}$$\vec l_{n_1,n_2} \in \mathbb R^{d_E}$，其中 $d_N$$d_N$ 为节点标签的维度、$d_E$$d_E$ 为边标签的维度。

   • 定义 $\overrightarrow{l}$$\vec l$ 为图中所有标签向量（包括所有节点标签向量、所有边标签向量）拼接得到的all 标签向量。

   • 标签向量的符号遵循更一般的scheme：如果 $\overrightarrow{\mathbf{y}}$$\mathbf{\vec y}$ 是图 $\mathbf{G}$$\mathbf G$ 中的某种类型的标签向量（如节点标签向量或边标签向量），$\mathbf{S}$$\mathbf S$ 为图 $\mathbf{G}$$\mathbf G$ 中的某个集合（如节点集合或边集合），则 ${\overrightarrow{\mathbf{y}}}_{\mathbf{S}}$$\mathbf{\vec y}_\mathbf S$ 为根据集合 $\mathbf{S}$$\mathbf S$ 获得的标签向量。例如 ${\overrightarrow{l}}_{\text{ne}[n]}$$\vec l_{\text{ne}[n]}$ 包含节点 $n$$n$ 的邻域节点的所有节点标签。

   注意，这里的符号定义与大多数论文的符号定义不同。

2. 节点标签通常包含节点的特征，边标签通常包含节点之间关系的特征。如下图中：节点标签可能代表区块的属性，如：面积、周长、颜色的平均强度。边标签可能代表区块（region）之间的相对位置，如：重心之间的距离、轴线之间的角度。我们未对边作出任何假设，有向边和无向边都是允许的。但是，当不同类型的边共同存在于同一个图 $\mathbf{G}$$\mathbf G$ 中时，就需要区分它们。这可以通过在每条边上添加适当的标签来轻松地实现，此时，不同类型的边具有不同的标签。

   

3. 图 $\mathbf{G}$$\mathbf G$ 可以是 positional 的、或者是 nonpositional 的。nonpositional graph 是前面所讲的那些图。positional graph 与之不同，节点 $n$$n$ 的每个邻居都被分配一个 unique 的整数标识符，从而指示每个邻居的逻辑位置（logical position ）。 形式上，对于positional graph 中的每个节点，存在一个映射函数 ${\nu }_n:\text{ne}[n]\to \{1,2,\cdots ,|\mathbf{N}|\}$$\nu_n:\text{ne}[n]\rightarrow \{1,2,\cdots,|\mathbf N|\}$，它为节点 $n$$n$ 的每个邻居节点 $u$$u$ 分配了一个位置 position ${\nu }_n(u)$$\nu_n(u)$ 。注意，邻居的位置可以用于隐式地存储有用的信息。例如，考虑区块邻接图（region adjacency graph）（如上图所示） ：可以用 ${\nu }_n$$\nu_n$ 来表示区块的相对空间位置，例如，${\nu }_n$$\nu_n$ 可能会按照顺时针的排序约定来枚举节点 $n$$n$ 的邻居。

   注意，位置信息可以通过对邻居节点分配位置编号来显式地给出，也可以通过对邻居节点进行排序从而隐式地给出。

4. 本文考虑的领域是 (graph, node) pair 的集合 $\mathcal{D}=\mathcal{G}\times \mathcal{N}$$\mathcal D = \mathcal G\times \mathcal N$ ，其中 $\mathcal{G}=\{{\mathbf{G}}_1,\cdots \}$$\mathcal G=\{\mathbf G_1,\cdots\}$ 为 graph 的集合，$\mathcal{N}=\{{\mathbf{N}}_1,\cdots \}$$\mathcal N=\{\mathbf N_1,\cdots\}$ 为这些 graph 的节点集合的集合，即：

   $$\mathcal{L}=\{({\mathbf{G}}_i,n_{i,j},{\mathbf{t}}_{i,j})\mid {\mathbf{G}}_i=({\mathbf{N}}_i,{\mathbf{E}}_i)\in \mathcal{G},n_{i,j}\in {\mathbf{N}}_i,{\mathbf{t}}_{i,j}\in {\mathbb{R}}^m,1\le i\le p,1\le j\le q_i\}$$

   其中：${\mathbf{G}}_i$$\mathbf G_i$ 表示第 $i$$i$ 个图，$n_{i,j}$$n_{i,j}$ 表示图 ${\mathbf{G}}_i$$\mathbf G_i$ 的第 $j$$j$ 个节点，${\mathbf{t}}_{i,j}$$\mathbf t_{i,j}$ 表示节点 $n_{i,j}$$n_{i,j}$ 的desired target （可能为向量也可能为标量），$p\le |\mathcal{G}|$$p\le |\mathcal G|$ ，$q_i\le |{\mathbf{N}}_i|$$q_i\le |\mathbf N_i|$ 。

   有趣的是，$\mathcal{D}$$\mathcal D$ 中所有的图都可以组合成一个 unique 的、断开的大图，因此可以将 $\mathcal{D}$$\mathcal D$ 视为一个 pair $\mathcal{L}=(\mathbf{G},\mathcal{T})$$\mathcal L = (\mathbf G,\mathcal T)$ ，其中：$\mathbf{G}=(\mathbf{N},\mathbf{E})$$\mathbf G=(\mathbf N,\mathbf E)$ 为包含所有节点和所有边的大图，$\mathcal{T}=\{(n_i,{\mathbf{t}}_i)\mid n_i\in \mathbf{N},{\mathbf{t}}_i\in {\mathcal{R}}^m,1\le i\le q\}$$\mathcal T = \left\{\left(n_i,\mathbf t_i\right)\mid n_i\in \mathbf N,\mathbf t_i\in \mathcal R^m,1\le i\le q\right\}$ 。值得一提的是，这个紧凑的定义不仅因为它简单易用，而且它还直接捕捉到了一些问题的本质，其中领域domain 仅由一个图组成，如大部分的 web 网络（如下图所示）。

   

1.1.1 思想

1. 我们所提出方法的直观想法是：图中的节点代表对象或概念，而边代表它们之间的关系。每个概念自然地由它的特征和相关的概念来定义。因此，我们可以可以将一个状态向量（state vector） ${\overrightarrow{\mathbf{x}}}_n\in {\mathcal{R}}^s$$\mathbf{\vec x}_n\in \mathcal R^s$ 关联到每个节点 $n$$n$ 上，其中 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 基于节点 $n$$n$ 的邻域信息来构建（如下图所示），$s$$s$ 为状态向量的维度。状态向量 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 包含由 $n$$n$ 表示的概念的 representation，并可用于产生输出 ${\overrightarrow{\mathbf{o}}}_n$$\mathbf{\vec o}_n$ （即，这个概念能决定什么）。

   令 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 为一个参数化（parametric）的函数，称之为局部转移函数（ local transition function ），用于表示节点对其邻域的依赖性。令 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 为另一个参数化的函数，称之为局部输出函数 （local output function），用于描述如何产生输出。那么 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 和 ${\overrightarrow{\mathbf{o}}}_n$$\mathbf{\vec o}_n$ 的定义如下：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

   其中：

   • ${\overrightarrow{l}}_n$$\vec l_n$ 为节点 $n$$n$ 的标签信息向量。

   • ${\overrightarrow{l}}_{\text{co}[n]}$$\vec l_{\text{co}[n]}$ 为包含节点 $n$$n$ 的所有边的标签信息向量拼接的向量。

   • ${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$\mathbf{\vec x}_{\text{ne}[n]}$ 为节点 $n$$n$ 的所有邻居的状态向量拼接的向量。

   • ${\overrightarrow{l}}_{\text{ne}[n]}$${\vec l}_{\text{ne}[n]}$ 为节点 $n$$n$ 的所有邻居的标签信息向量拼接的向量。

   注意：这里有递归定义，其中节点 $n$$n$ 的状态向量 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 依赖于其邻居的状态向量集合 ${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$\mathbf{\vec x}_{\text{ne}[n]}$ 。而邻居的状态向量又依赖于邻居的邻居的状态向量集合。

   注意：这里的邻域依赖性使得计算状态向量所依赖的节点规模迅速膨胀。假设平均邻域大小为 10 个节点，如果最多依赖于 5 阶邻域，那么计算每个状态向量需要依赖于 5 阶邻域内的 10 万个邻域节点。

   备注：

   • 备注一：可以采用不同的邻域概念。例如，人们可能希望删除标签 ${\overrightarrow{l}}_{\text{ne}[n]}$$\vec l_{\text{ne}[n]}$，因为 ${\overrightarrow{l}}_{\text{ne}[n]}$$\vec l_{\text{ne}[n]}$ 的信息可能隐含在 ${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$\mathbf{\vec x}_{\text{ne}[n]}$ 中。此外，邻域可能包含距 $n$$n$ 2-hop 或者多个 hop 的节点。

   • 备注二：上式用于无向图。在处理有向图时，函数 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 也可以接受链接的方向作为输入。我们引入一个变量 $d_e,\mathit{e}\in \text{co}[n]$$d_e, \mathit e \in \text{co}[n]$：如果边 $e$$e$ 的终点为 $n$$n$ 则 $d_e=1$$d_e = 1$，如果边 $e$$e$ 的起点为 $n$$n$ 则 $d_e=0$$d_e = 0$。则有：

     $${\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\mathbf{d}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})$$

     本文中为了保持符号紧凑，我们使用无向图的形式。然而，除非特殊说明，否则本文中提出的所有结果也适用于有向图、以及混合有向与无向的图。

   • 备注三：通常而言，转移函数 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和输出函数 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 以及它们的参数（parameters）可能都依赖于节点 $n$$n$ 。但是在一些场景中，节点分为不同类型，并且不同类型的节点有不同的转移函数、输出函数、以及它们的参数。假设节点 $n$$n$ 的类别为 $k_n$$k_n$ ，转移函数为 $f_{\mathbf{w}}^{k_n}(\cdot )$$f_{\mathbf w}^{k_n}(\cdot)$，输出函数为 $g_{\mathbf{w}}^{k_n}(\cdot )$$g_{\mathbf w}^{k_n}(\cdot)$，对应参数为 ${\mathbf{w}}_{k_n}$$\mathbf w_{k_n}$，则有：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{{\mathbf{w}}_{k_n}}^{k_n}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{{\mathbf{w}}_{k_n}}^{k_n}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

     然而为了简单起见，我们对所有节点共享相同的转移函数和输出函数（包括它们的参数）。

     如果没有参数共享则模型的容量太大导致难以训练且很容易过拟合。

   

2. 令 $\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{o}},\overrightarrow{l},{\overrightarrow{l}}_{\mathbf{N}}$$\mathbf{\vec x}, \mathbf{\vec o},\vec l,\vec l_{\mathbf N}$ 分别代表所有节点状态向量的拼接、所有节点输出向量的拼接、所有标签（包含节点标签以及边的标签）向量的拼接、所有节点标签向量的拼接（例如，$\overrightarrow{\mathbf{x}}={[{\overrightarrow{\mathbf{x}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{x}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}$$\mathbf{\vec x}=\left[\mathbf{\vec x}_1^\top,\cdots,\mathbf{\vec x}_{|\mathbf N|}^\top\right]^\top$），则有：

   $$\begin{array}{c}\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})\\ \overrightarrow{\mathbf{o}}=G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})\end{array}$$

   其中：

   • $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 称作全局转移函数 （global transition fucntion），它由 $|\mathbf{N}|$$|\mathbf N|$ 个 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 组成。

   • $G_{\mathbf{w}}(\cdot )$$G_{\mathbf w}(\cdot)$ 称作全局输出函数 （global output function），它由 $|\mathbf{N}|$$|\mathbf N|$ 个 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 组成。

   令图和节点的 pair 对的集合为 $\mathcal{D}=\mathcal{G}\times \mathcal{N}$$\mathcal D = \mathcal G\times \mathcal N$，其中 $\mathcal{G}=\{{\mathbf{G}}_1,\cdots \}$$\mathcal G=\{\mathbf G_1,\cdots\}$ 为所有图的集合，$\mathbf{N}=\{{\mathbf{N}}_1,\cdots \}$$\mathbf N=\{\mathbf N_1,\cdots\}$ 为这些图中所有节点的集合。全局转移函数和全局输出函数定义了一个映射 ${\phi }_{\mathbf{w}}:\mathcal{D}\to {\mathcal{R}}^m$$\varphi_{\mathbf w}: \mathcal D \rightarrow \mathcal R^m$ ，它以一个图作为输入，然后对每个节点 $n$$n$ 返回一个输出 ${\overrightarrow{\mathbf{o}}}_n$$\mathbf{\vec o}_n$ 。

   Banach 不动点理论（ fixed point theorem ）为上述方程解的存在性和唯一性提供了理论依据。根据 Banach不动点理论，当 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 满足以下条件时，方程 $\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$\mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right)$ 存在唯一解：$F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是一个收缩映射 （contraction map）。即存在 $\mu ,0\le \mu <1$$\mu, 0\le\mu\lt 1$，使得对任意 $\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{y}}$$\mathbf{\vec x}, \mathbf{\vec y}$ 都有：

   $$\Vert F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})-F_{\mathbf{w}}(\overrightarrow{\mathbf{y}},\overrightarrow{l})\Vert \le \mu \Vert \overrightarrow{\mathbf{x}}-\overrightarrow{\mathbf{y}}\Vert$$

   其中 $||\cdot ||$$||\cdot||$ 表示向量范数。

   本文中我们假设 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是一个收缩映射。实际上在 GNN 模型中，这个条件是通过适当的选择转移函数来实现的。

3. 上述公式能够同时处理位置图（positional graph）和非位置图（nonpositional graph）。

   • 对于位置图，$f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 必须接收每个邻域节点的位置作为额外的输入。实际中我们可以根据邻居的位置进行排序，然后对 ${\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]}$$\vec l_{\text{co}[n]}, \mathbf{\vec x}_{\text{ne}[n]}, \vec l_{\text{ne}[n]}$ 按照排序之后的顺序进行拼接。如果在某些位置处的邻居不存在，则需要填充 null 值。例如：

     $${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}={[{\overrightarrow{\mathbf{y}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{y}}}_M^{\mathrm{\top }}]}^{\mathrm{\top }}$$

     其中：

     • $M=\underset{n,u}{max}{\nu }_n(u)$$M = \max_{n,u}\nu_n(u)$ 为所有节点的最大邻居数。

     • ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 为第 $i$$i$ 个位置邻居的状态向量：

       $$\begin{array}{c}{\overrightarrow{\mathbf{y}}}_i=\{\begin{array}{ll}{\overrightarrow{\mathbf{x}}}_u& \text{if}(i={\nu }_n(u))\\ {\overrightarrow{\mathbf{x}}}_0& \text{else}\end{array}\end{array}$$

       即：如果 $u$$u$ 为节点 $n$$n$ 的第 $i$$i$ 个邻居节点，则 ${\overrightarrow{\mathbf{y}}}_i={\overrightarrow{\mathbf{x}}}_u$$\mathbf{\vec y}_i = \mathbf{\vec x}_u$；如果节点 $n$$n$ 没有第 $i$$i$ 个邻居节点，则 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf{\vec y}_i$ 为null 值 ${\overrightarrow{\mathbf{x}}}_0$$\mathbf{\vec x}_0$ 。

   • 对于位置无关的图，我们可以将 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 替换为：

     $${\overrightarrow{\mathbf{x}}}_n=\sum _{u\in \text{ne}[n]}{h}_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)$$

     其中 $h_{\mathbf{w}}(\cdot )$$h_{\mathbf w}(\cdot)$ 为待学习的函数，它和邻居节点的数量和位置无关。这种形式被称作 nonpositional form，而原始形式被称作 positional form。

     注意，这里对邻居节点采用 sum 聚合。也可以采用 max 聚合或者 attention 聚合。

4. 为实现 GNN 模型，我们必须解决以下问题：

   • 求解以下方程的算法：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

   • 从训练集中学习 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 参数的学习算法。

   • $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 的实现方式，即：解空间。

1.1.2 方程求解算法

1. Banach 不动点理论不仅保证了解的存在性和唯一性，还给出了求解的方式：采用经典的迭代式求解：

   $$\overrightarrow{\mathbf{x}}(t+1)=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}}(t),\overrightarrow{l})$$

   其中 $\overrightarrow{\mathbf{x}}(t)$$\mathbf{\vec x}(t)$ 表示状态 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的第 $t$$t$ 次迭代值。

   对于任意初始值 $\overrightarrow{\mathbf{x}}(0)$$\mathbf{\vec x}(0)$ ，上式指数级收敛到方程 $\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$\mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right)$ 的解。我们将 $\overrightarrow{\mathbf{x}}(t)$$\mathbf{\vec x}(t)$ 视为状态向量，它由转移函数 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 来更新。因此输出向量 ${\overrightarrow{\mathbf{o}}}_n(t)$$\mathbf{\vec o}_n(t)$ 和状态向量 ${\overrightarrow{\mathbf{x}}}_n(t)$$\mathbf{\vec x}_n(t)$ 的更新方程为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n(t+1)=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}(t),{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n(t)=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n(t),{\overrightarrow{l}}_n),n\in \mathbf{N}\end{array}$$

   这可以解释为由很多处理单元（unit ）组成的神经网络，每个处理单元通过 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 计算其状态，并通过 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 计算其输出。这个神经网络被称作编码网络 （encoding network），它类似于 RNN 的编码网络。在编码网络中，每个单元根据邻居单元的状态、当前节点的信息、邻居节点的信息、边的信息，通过 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 计算下一个时刻的状态 ${\overrightarrow{\mathbf{x}}}_n(t+1)$$\mathbf{\vec x}_n(t+1)$ 。

2. 当 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 通过前馈神经网络实现时，编码网络就成为 RNN ，其中神经元之间的连接可以分为内部连接（internal connection）和外部连接（external connection）：内部连接由实现处理单元的神经网络架构（如前馈神经网络）决定，外部连接由图的边来决定。

   如下图所示：上半图对应一个Graph，中间图对应于编码网络，下半图对应于编码网络的展开图（unfolding graph ）。在展开图中，每一层（layer）代表一个时间步，layer 之间的链接（外部连接）由图的连接性来决定，layer 内神经元的链接（内部连接）由神经网络架构决定。

   内部连接决定 $f_{\mathbf{w}}(\cdot )$$f_\mathbf w(\cdot)$ 如何更新状态 ${\overrightarrow{\mathbf{x}}}_n(t)$$\mathbf{\vec x}_n(t)$ ，外部连接决定节点之间的依赖关系。

   

1.1.3 参数学习算法

1. 假设训练集为：

   $$\begin{array}{c}\mathcal{L}=\{({\mathbf{G}}_i,n_{i,j},{\mathbf{t}}_{i,j})\mid {\mathbf{G}}_i=({\mathbf{N}}_i,{\mathbf{E}}_i)\in \mathcal{G},n_{i,j}\in {\mathbf{N}}_i,{\mathbf{t}}_{i,j}\in {\mathbb{R}}^m,1\le i\le p,1\le j\le q_i\}\\ p\le |\mathcal{G}|,q_i\le |{\mathbf{N}}_i|\end{array}$$

   其中： ${\mathbf{G}}_i$$\mathbf G_i$ 表示第 $i$$i$ 个图，${\mathbf{N}}_i$$\mathbf N_i$ 表示第 $i$$i$ 个图的节点集合，${\mathbf{E}}_i$$\mathbf E_i$ 表示第 $i$$i$ 个图的边集合，$n_{i,j}$$n_{i,j}$ 表示第 $i$$i$ 个图的第 $j$$j$ 个节点，${\mathbf{t}}_{i,j}$$\mathbf t_{i,j}$ 表示节点 $n_{i,j}$$n_{i,j}$ 的监督信息target （可能为标量可能为向量），$q_i$$q_i$ 为图 ${\mathbf{G}}_i$$\mathbf G_i$ 中的标记样本数量，$p$$p$ 为数据集中图的数量。

   • 对于 graph-focused 任务，可以引入一个和任务目标相关的、特殊的节点，只有该节点包含监督信息，即 $q_i=1$$q_i = 1$ 。

   • 对于node-focused 任务，每个节点都可以包含监督信息。

   假设采用平方误差，则训练集的损失函数为：

   $$e_{\mathbf{w}}=\sum _{i=1}^p\sum _{j=1}^{q_i}{\Vert {\mathbf{t}}_{i,j}-{\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})\Vert }_2^2$$

   其中 ${\phi }_{\mathbf{w}}(\cdot )$$\varphi_\mathbf{w}(\cdot)$ 为近似函数 （approximate function）。

   也可以在损失函数中增加罚项从而对模型施加约束。

2. 我们可以基于梯度下降算法来求解该最优化问题，求解方法由以下几步组成：

   • 通过下面的迭代公式求解求解 ${\overrightarrow{\mathbf{x}}}_n(t)$$\mathbf{\vec x}_n(t)$，直到时间 $T$$T$ ：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n(t+1)=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}(t),{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n(t)=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n(t),{\overrightarrow{l}}_n),n\in \mathbf{N}\end{array}$$

     其解接近 $\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$\mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right)$ 的不动点 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$，即：$\overrightarrow{\mathbf{x}}(T)\simeq {\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}(T) \simeq \mathbf{\vec x}^*$ 。

     注意：这一步要求 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是一个压缩映射，从而保证方程能够收敛到一个不动点。

   • 求解梯度 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\nabla_{\mathbf{ w}} e_{\mathbf w}$ 。

   • 通过梯度来更新参数$\mathbf{w}$$\mathbf w$ 。

3. 梯度 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\nabla_{\mathbf{ w}} e_{\mathbf w}$ 的计算可以利用 GNN 中发生的扩散过程（diffusion process）以非常高效的方式进行。这种扩散过程与 RNN 中发生的扩散过程非常相似，而后者是基于backpropagation-through-time: BPTT 算法计算梯度的。在这种情况下，编码网络从时刻 $T$$T$ 展开unfold 到初始时刻 $t_0$$t_0$ 。展开图如上图所示，每一层对应于一个时刻，并且包含编码网络中所有单元unit $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的副本。连续两层之间按照图的连通性进行链接。对应于时刻 $T$$T$ 的最后一层也包括单元 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 并计算网络的输出。

   BPTT 是在展开图上执行传统的反向传播算法。 首先计算时间步 $T$$T$ 的损失函数，以及损失函数在每个时间步 $t$$t$ 相对于 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 的梯度。最终 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}(T)$$\nabla_{\mathbf{ w}} e_{\mathbf w}(T)$ 由所有时间步的梯度之和得到。然而，BPTT 要求存储每个单元在每个时间步 $t$$t$ 的状态 $\overrightarrow{\mathbf{x}}(t)$$\mathbf {\vec x}(t)$，当 $T-t_0$$T-t_0$ 非常大时内存需求太大。为解决该问题，我们基于 Almeida-Pineda 算法提出了一个非常高效的处理方式：由于我们假设状态向量 $\overrightarrow{\mathbf{x}}(t)$$\mathbf{\vec x}(t)$ 最终收敛到不动点 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$，因此我们假设对于任意 $t\ge t_0$$t\ge t_0$ 都有 $\overrightarrow{\mathbf{x}}(t)={\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}(t) = \mathbf{\vec x}^*$ 。因此 BPTT 算法仅需要存储 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$ 即可。

   下面两个定理表明这种简单直观方法的合理性：

   • 定理（可微性Differentiability）：如果全局转移函数 $F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right)$ 和全局输出函数 $G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})$$G_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}_\mathbf N\right)$ 对于状态 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 和参数 $\mathbf{w}$$\mathbf{w}$ 都是连续可微的，则 ${\phi }_{\mathbf{w}}$$\varphi_{\mathbf w}$ 对于参数 $\mathbf{w}$$\mathbf{w}$ 也是连续可微的。

     其证明见原始论文。值得注意的是，对于一般动力学系统而言该结论不成立。对于这些动力学系统而言，参数的微小变化会迫使其从一个固定点转移到另一个固定点。而 GNN 中的 ${\phi }_{\mathbf{w}}$$\varphi_{\mathbf w}$ 可微的原因是由于 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是收缩映射。

   • 定理：如果全局转移函数 $F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right)$ 和全局输出函数 $G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})$$G_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}_\mathbf N\right)$ 对于状态 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 和参数 $\mathbf{w}$$\mathbf{w}$ 都是连续可微的，定义 $\overrightarrow{\mathbf{z}}(t)\in {\mathcal{R}}^s$$\mathbf{\vec z}(t) \in \mathcal R^s$ 为：

     $$\overrightarrow{\mathbf{z}}(t)={\left(\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}\overrightarrow{\mathbf{z}}(t+1)+{\left(\frac{\partial G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}(t)$$

     则序列 $\overrightarrow{\mathbf{z}}(T),\overrightarrow{\mathbf{z}}(T-1),\cdots$$\mathbf{\vec z}(T),\mathbf{\vec z}(T-1),\cdots$ 以指数级收敛到一个向量 ${\overrightarrow{\mathbf{z}}}^{\ast }=\underset{t\to -\mathrm{\infty }}{lim}\overrightarrow{\mathbf{z}}(t)$$\mathbf{\vec z}^* = \lim_{t\rightarrow -\infty} \mathbf{\vec z}(t)$，且收敛结果和初始状态 $\overrightarrow{\mathbf{z}}(T)$$\mathbf{\vec z}(T)$ 无关。

     更进一步有：

     $${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}={\left(\frac{\partial G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}+{\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}^{\ast }$$

     其中 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$ 为GNN 的不动点，${\overrightarrow{\mathbf{z}}}^{\ast }$$\mathbf{\vec z}^*$ 为上述收敛的向量。

     证明见论文原文。

     第一项表示输出函数 $G_{\mathbf{w}}(\cdot )$$G_{\mathbf w}(\cdot)$ 对于梯度的贡献，反向传播的梯度在通过 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 的 layer 时计算这一项。第二项表示转移函数 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 对于梯度的贡献，反向传播的梯度在通过 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的 layer 时计算这一项。

4. GNN 参数学习算法包含三个部分：

   • FORWARD前向计算部分：前向计算部分用于计算状态向量 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$，即寻找不动点。该部分迭代直到 $\Vert \overrightarrow{\mathbf{x}}(t)-\overrightarrow{\mathbf{x}}(t-1)\Vert$$\left\|\mathbf{\vec x}(t) - \mathbf{\vec x}(t-1)\right\|$ 小于给定的阈值。

   • BACKWARD 反向计算部分：反向计算部分用于计算梯度 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\nabla_{\mathbf{w}} e_{\mathbf w}$ 。该部分迭代直到 $\Vert \overrightarrow{\mathbf{z}}(t-1)-\overrightarrow{\mathbf{z}}(t)\Vert$$\left\|\mathbf{\vec z}(t-1) - \mathbf{\vec z}(t)\right\|$ 小于给定的阈值。

   • MAIN 部分：该部分用于求解参数。该部分更新权重 $\mathbf{w}$$\mathbf{w}$ 直到满足迭代的停止标准。

5. FORWARD 部分：

   • 输入：图 $\mathbf{G}=(\mathbf{N},\mathbf{E})$$\mathbf G = (\mathbf N,\mathbf E)$，当前参数 $\mathbf{w}$$\mathbf{w}$，迭代停止条件 ${ϵ}_f$$\epsilon_f$

   • 输出：不动点 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$

   • 算法步骤：

     • 随机初始化 $\overrightarrow{\mathbf{x}}(0)$$\mathbf{\vec x}(0)$，令 $t=0$$t=0$ 。

     • 循环迭代，直到满足 $\Vert \overrightarrow{\mathbf{x}}(t)-\overrightarrow{\mathbf{x}}(t-1)\Vert \le {ϵ}_f$$\left\|\mathbf{\vec x}(t) - \mathbf{\vec x}(t-1)\right\|\le \epsilon_f$。迭代步骤为：

       • 计算 $\overrightarrow{\mathbf{x}}(t+1)$$\mathbf{\vec x}(t+1)$： $\overrightarrow{\mathbf{x}}(t+1)=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}}(t),\overrightarrow{l})$$\mathbf{\vec x}(t+1) = F_{\mathbf w}\left(\mathbf{\vec x}(t),\vec l\right)$ 。

       • 令 $t=t+1$$t = t+1$ 。

     • 返回 ${\overrightarrow{\mathbf{x}}}^{\ast }(t)$$\mathbf{\vec x}^*(t)$ 。

6. BACKWARD 部分：

   • 输入：图 $\mathbf{G}=(\mathbf{N},\mathbf{E})$$\mathbf G=(\mathbf N,\mathbf E)$，不动点 ${\overrightarrow{\mathbf{x}}}^{\ast }$$\mathbf{\vec x}^*$，当前参数 $\mathbf{w}$$\mathbf{w}$，迭代停止条件 ${ϵ}_b$$\epsilon_b$

   • 输出：梯度 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\nabla_{\mathbf{w}}e_{\mathbf w}$

   • 算法步骤：

     • 定义：

       $$\overrightarrow{\mathbf{o}}=G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})\mathbf{A}={\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }},\overrightarrow{\mathbf{b}}={\left(\frac{G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}$$

     • 随机初始化 $\overrightarrow{\mathbf{z}}(T)$$\mathbf{\vec z}(T)$，令 $t=T$$t = T$ 。

     • 循环迭代，直到满足 $\Vert \overrightarrow{\mathbf{z}}(t-1)-\overrightarrow{\mathbf{z}}(t)\Vert \le {ϵ}_b$$\left\|\mathbf{\vec z}(t-1) - \mathbf{\vec z}(t)\right\|\le \epsilon_b$ 从而得到收敛的 ${\overrightarrow{\mathbf{z}}}^{\ast }$$\mathbf{\vec z}^*$。迭代步骤为：

       • 更新 $\overrightarrow{\mathbf{z}}(t)$$\mathbf{\vec z}(t)$ ：$\overrightarrow{\mathbf{z}}(t)=\mathbf{A}\overrightarrow{\mathbf{z}}(t+1)+\overrightarrow{\mathbf{b}}$$\mathbf{\vec z}(t) = \mathbf A\mathbf{\vec z}(t+1) + \mathbf{\vec b}$ 。

       • 令 $t=t-1$$t = t - 1$ 。

     • 计算梯度：

       $${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}={\left(\frac{\partial G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}+{\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}^{\ast }$$

     • 返回梯度 ${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\nabla_{\mathbf{w}}e_{\mathbf w}$ 。

7. Main 部分：

   • 输入：图 $\mathbf{G}=(\mathbf{N},\mathbf{E})$$\mathbf G=(\mathbf N,\mathbf E)$ ，学习率 $\lambda$$\lambda$

   • 输出：模型参数 $\mathbf{w}$$\mathbf{w}$

   • 算法步骤：

     • 随机初始化参数 $\mathbf{w}$$\mathbf{w}$ 。

     • 通过前向计算过程计算状态：${\overrightarrow{\mathbf{x}}}^{\ast }=\text{Forward}(\mathbf{w})$$\mathbf{\vec x}^* = \text{Forward}(\mathbf{w})$ 。

     • 循环迭代，直到满足停止条件。循环步骤为：

       • 通过反向计算过程计算梯度：${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}=\text{Backward}({\overrightarrow{\mathbf{x}}}^{\ast },\mathbf{w})$$\nabla_{\mathbf{w}} e_{\mathbf w} = \text{Backward}\left(\mathbf{\vec x}^*,\mathbf{w}\right)$

       • 更新参数：$\mathbf{w}=\mathbf{w}-\lambda {\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$\mathbf{w} = \mathbf{w} - \lambda \nabla_{\mathbf{w}} e_{\mathbf w}$ 。

       • 通过新的参数计算状态：${\overrightarrow{\mathbf{x}}}^{\ast }=\text{Forward}(\mathbf{w})$$\mathbf{\vec x}^* = \text{Forward}(\mathbf{w})$ 。

     • 返回参数 $\mathbf{w}$$\mathbf{w}$ 。

8. Main 部分采用预定义的学习率 $\lambda$$\lambda$，但是也可以使用基于梯度下降的一些通用策略，例如使用带动量的梯度更新 、或者自适应学习率的方案。另一方面，目前 GNN 只能通过梯度下降算法求解，非梯度下降算法目前还未解决，这是未来研究的方向。

9. 实际上编码网络仅仅类似于静态的前馈神经网络，但是编码网络的层数是动态确定的（类似于 RNN ），并且网络权重根据输入图的拓扑结构来共享。因此为静态网络设计的二阶学习算法、剪枝算法、以及逐层学习算法无法直接应用于 GNN 。

1.1.4 转移函数和输出函数

1. 局部输出函数 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 的实现没有任何约束。通常在 GNN 中，$g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 采用一个多层前馈神经网络来实现。

   另一方面，局部转移函数 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 在 GNN 中起着关键作用，它决定了不动点的存在性和唯一性。GNN 的基本假设是：全局转移函数 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是收缩映射。接下来，我们给出了两种满足该约束的 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的实现，它们都是基于nonpositional form，positional form 也可以类似地实现。

2. nonpositional linear GNN ：

   $$h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)={\mathbf{A}}_{n,u}{\overrightarrow{\mathbf{x}}}_u+{\overrightarrow{\mathbf{b}}}_n$$

   其中 ${\overrightarrow{\mathbf{b}}}_n\in {\mathcal{R}}^s$$\mathbf{\vec b}_n\in \mathcal R^s$ 和矩阵 ${\mathbf{A}}_{n,u}\in {\mathcal{R}}^{s\times s}$$\mathbf A_{n,u}\in \mathcal R^{s\times s}$ 分别由两个前馈神经网络的输出来定义，这两个前馈神经网络的参数对应于 GNN 的参数。更准确的说：

   • 转移网络 （transition network）是一个前馈神经网络，它用于生成 ${\mathbf{A}}_{n,u}$$\mathbf A_{n,u}$ 。

     设该神经网络为一个映射 ${\varphi }_{\mathbf{w}}:{\mathcal{R}}^{2d_N+d_E}\to {\mathcal{R}}^{s^2}$$\phi_{\mathbf w}:\mathcal R^{2d_N+d_E} \rightarrow \mathcal R^{s^2}$，则定义：

     $${\mathbf{A}}_{n,u}=\frac{\mu }{s\times |\text{ne}[u]|}\mathbf{B}$$

     其中：

     • $\mathbf{B}\in {\mathcal{R}}^{s\times s}$$\mathbf B\in \mathcal R^{s\times s}$ 是由 ${\varphi }_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{n,u},{\overrightarrow{l}}_u)$$\phi_{\mathbf w}\left(\vec l_n,\vec l_{n,u},\vec l_u\right)$ 的 $s^2$$s^2$ 个元素进行重新排列得到的矩阵。

     • $\mu \in (0,1)$$\mu\in (0,1)$ 为缩放系数，$\frac{\mu }{s\times |\text{ne}[u]|}$$\frac{\mu}{s\times |\text{ne}[u]|}$ 用于对矩阵 $\mathbf{B}$$\mathbf B$ 进行缩放。

     因此 ${\mathbf{A}}_{n,u}$$\mathbf A_{n,u}$ 是对转移网络输出的重排方阵 $\mathbf{B}$$\mathbf B$ 进行缩放得到。

     这里的转移矩阵 ${\mathbf{A}}_{n,u}$$\mathbf A_{n,u}$ 是神经网络的输出，而不是待学习的权重参数。这是因为可以选择输出函数（如 tanh），使得神经网络的输出满足某些性质，从而使得 $F_{\mathbf{w}}(\cdot )$$F_\mathbf w(\cdot)$ 为收缩映射。

   • 约束网络（forcing network）是另一个前馈神经网络，它用于生成 ${\overrightarrow{\mathbf{b}}}_n$$\mathbf{\vec b}_n$。

     设该神经网络为一个映射 ${\rho }_{\mathbf{w}}:{\mathcal{R}}^{d_N}\to {\mathcal{R}}^s$$\rho_{\mathbf w}: \mathcal R^{d_N} \rightarrow \mathcal R^s$，则定义：

     $${\overrightarrow{\mathbf{b}}}_n={\rho }_{\mathbf{w}}\left({\overrightarrow{l}}_n\right)$$

     因此，${\overrightarrow{\mathbf{b}}}_n$$\mathbf{\vec b}_n$ 为约束网络的输出构成的向量。

     这里 ${\overrightarrow{\mathbf{b}}}_n$$\mathbf{\vec b}_n$ 仅依赖于节点 $n$$n$ 本身的标签信息。

   假设有：${\Vert {\varphi }_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{n,u},{\overrightarrow{l}}_u)\Vert }_1\le s$$\left\|\phi_{\mathbf w}(\vec l_n,\vec l_{n,u},\vec l_u)\right\|_1 \le s$ ，即 $|\mathbf{B}{|}_1\le s$$|\mathbf B|_1 \le s$。事实上如果转移网络的输出神经元采用有界的激活函数（如tanh 激活函数），则很容易满足该假设。根据 $h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)={\mathbf{A}}_{n,u}{\overrightarrow{\mathbf{x}}}_u+{\overrightarrow{\mathbf{b}}}_n$$h_{\mathbf w} \left({\vec l}_n,{\vec l}_{(n,u)}, \mathbf{\vec x}_{u},{\vec l}_{u}\right) = \mathbf A_{n,u} \mathbf{\vec x}_u + \mathbf{\vec b}_n$ 有：

   $$F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})=\mathbf{A}\overrightarrow{\mathbf{x}}+\overrightarrow{\mathbf{b}}$$

   其中：

   • $\overrightarrow{\mathbf{b}}$$\mathbf{\vec b}$ 是由所有的 ${\overrightarrow{\mathbf{b}}}_n$$\mathbf{\vec b}_n$ 拼接而来，$\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 是由所有的 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 拼接而来：

     $$\overrightarrow{\mathbf{b}}={[{\overrightarrow{\mathbf{b}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{b}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}={[{\overrightarrow{\mathbf{x}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{x}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}$$

   • $\mathbf{A}$$\mathbf A$ 是一个分块矩阵，每一块为 ${\overline{\mathbf{A}}}_{n,u}$$\bar{\mathbf A}_{n,u}$ ：

     $$\begin{array}{c}\mathbf{A}=\left[\begin{array}{cccc}{\overline{\mathbf{A}}}_{1,1}& {\overline{\mathbf{A}}}_{1,2}& \cdots & {\overline{\mathbf{A}}}_{1,|\mathbf{N}|}\\ {\overline{\mathbf{A}}}_{2,1}& {\overline{\mathbf{A}}}_{2,2}& \cdots & {\overline{\mathbf{A}}}_{2,|\mathbf{N}|}\\ ⋮& ⋮& \ddots & ⋮\\ {\overline{\mathbf{A}}}_{|\mathbf{N}|,1}& {\overline{\mathbf{A}}}_{|\mathbf{N}|,2}& \cdots & {\overline{\mathbf{A}}}_{|\mathbf{N}|,|\mathbf{N}|}\end{array}\right]\end{array}$$

     其中：

     • 如果 $u$$u$ 是 $n$$n$ 的邻居节点，则有 ${\overline{\mathbf{A}}}_{n,u}={\mathbf{A}}_{n,u}$$\bar{\mathbf A}_{n,u} = \mathbf A_{n,u}$ 。

     • 如果 $u$$u$ 不是 $n$$n$ 的邻居节点，则由 ${\overline{\mathbf{A}}}_{n,u}=\mathbf{0}$$\bar{\mathbf A}_{n,u} = \mathbf 0$ 。

   由于 ${\overrightarrow{\mathbf{b}}}_n$$\mathbf{\vec b}_n$ 和 ${\mathbf{A}}_{n,u}$$\mathbf A_{n,u}$ 不依赖于状态 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$（它们仅仅依赖于图的结构和节点标签信息、边标签信息），因此有：

   $$\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}=\mathbf{A}$$

   则有：

   $${\Vert \frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\Vert }_1=||\mathbf{A}|{|}_1\le \underset{u\in \mathbf{N}}{max}(\sum _{n\in \text{ne}[u]}||{\mathbf{A}}_{n,u}|{|}_1)\le \underset{u\in \mathbf{N}}{max}(\frac{\mu }{s\times |\text{ne}[u]|}\times \sum _{n\in \text{ne}[u]}||\mathbf{B}|{|}_1)\le \mu$$

   因此对于任意的参数 $\mathbf{w}$$\mathbf{w}$，$F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 都是收缩映射。

3. nonpositional nonlinear GNN ：$h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)$$h_{\mathbf w} \left({\vec l}_n,{\vec l}_{(n,u)}, \mathbf{\vec x}_{u},{\vec l}_{u}\right)$ 通过一个多层前馈神经网络来实现。由于三层神经网络是通用的函数逼近器，可以逼近任何所需的函数。但是，并非所有的参数 $\mathbf{w}$$\mathbf w$ 都可以使用，因为必须保证对应的转移函数 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 是收缩映射。这可以通过在损失函数中增加罚项来实现：

   $$\begin{array}{c}{e}_{\mathbf{w}}=\sum _{i=1}^p\sum _{j=1}^{q_i}{\Vert {\mathbf{t}}_{i,j}-{\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})\Vert }_2^2+\beta L\left({\Vert \mathbf{A}\Vert }_1\right)\\ \mathbf{A}=\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\end{array}$$

   注意，这里针对关于 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的雅克比矩阵进行约束，而不是针对 $\mathbf{w}$$\mathbf w$ 的大小进行约束。

   其中：$\mathbf{A}$$\mathbf A$ 为 $F_{\mathbf{w}}(\cdot )$$F_\mathbf w(\cdot)$ 关于 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的雅克比矩阵；罚项 $L(\cdot )$$L(\cdot)$ 定义为：

   $$\begin{array}{c}L(y)=\{\begin{array}{ll}(y-\mu {)}^2& ,\text{if}y>\mu \\ 0& ,\text{else}\end{array}\end{array}$$

   超参数 $\mu \in (0,1)$$\mu \in (0,1)$ 定义了针对 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 的约束。

   更一般地，罚项可以是关于 $\mathbf{w}$$\mathbf w$ 可微的任何表达式，只需要关于雅克比范数 ${\Vert \mathbf{A}\Vert }_1$$\left\|\mathbf A\right\|_1$ 单调递增。例如，在我们的实验中，我们使用罚项 $p_{\mathbf{w}}=L(\parallel \mathbf{A}{\parallel }_1)=\sum _{i=1}^{s}L\left({\Vert {\mathbf{A}}^i\Vert }_1\right)$$p_{\mathbf w} =L(\|\mathbf A\|_1)= \sum_{i=1}^s L\left(\left\|\mathbf A^i\right\|_1\right)$，其中 ${\mathbf{A}}^i$$\mathbf A^i$ 为 $\mathbf{A}$$\mathbf A$ 的第 $i$$i$ 列。实际上这个罚项是 $L\left(\underset{i}{max}{\Vert {\mathbf{A}}^i\Vert }_1\right)$$L\left(\max_i\left\|\mathbf A^i\right\|_1\right)$ 的一个近似。

1.2 模型分析

1. GNN 和 RNN：事实上，GNN 是其它已知模型的扩展，特别地，RNN 是 GNN 的特例。当满足以下条件时，GNN 退化为 RNN：

   • 输入图为有向无环图（例如最简单的有向的、线性的链式图）。

   • $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的输入为 ${\overrightarrow{l}}_n,{\overrightarrow{\mathbf{x}}}_{\text{ch}[n]}$$\vec l_n, \mathbf{\vec x}_{\text{ch}[n]}$ ，其中 $\text{ch}[n]$$\text{ch}[n]$ 为节点 $n$$n$ 的子结点的集合。

   • 一个超级源点 $\text{sn}$$\text{sn}$，从该源点可以到达其它所有节点。该源点通常对应于 graph-focused 任务的输出 ${\overrightarrow{\mathbf{o}}}_{\text{sn}}$$\mathbf{\vec o}_\text{sn}$ 。

   实现 $f_{\mathbf{w}}(\cdot ),g_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot),g_{\mathbf w}(\cdot)$ 的神经网络形式包括：多层前馈神经网络、cascade correlation、自组织映射 （self-orgnizing map）。在 RNN 中，编码网络采用多层前馈神经网络。这个简化了状态向量的计算。

2. GNN 和随机游走：当选择 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 为线性函数时，GNN 模型还捕获了图上的随机游走过程。

   定义节点的状态 ${\overrightarrow{\mathbf{x}}}_n$$\mathbf{\vec x}_n$ 为一个实数，其定义为：

   $$x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$

   其中： $\text{pa}[n]$$\text{pa}[n]$ 表示节点 $n$$n$ 的父节点集合；$a_{n,i}$$a_{n,i}$ 为归一化系数，满足：

   $$a_{n,i}\ge 0,\sum _{i\in \text{pa}[n]}{a}_{n,i}=1$$

   事实上 $x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$x_n = \sum_{i\in \text{pa}[n]} a_{n,i}\times x_i$ 定义了一个随机游走生成器：

   • $a_{n,i}$$a_{n,i}$ 表示当前位于节点 $n$$n$ 时，随机转移到下一个节点 $i$$i$ 的概率。

   • $x_n$$x_n$ 表示当系统稳定时，随机游走生成器位于节点 $n$$n$ 的概率。

   当所有的 $x_n$$x_n$ 拼接成向量 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$，则有：

   $$\begin{array}{c}\overrightarrow{\mathbf{x}}=\mathbf{A}\overrightarrow{\mathbf{x}}\\ \overrightarrow{\mathbf{x}}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{|\mathbf{N}|}\end{array}\right]\mathbf{A}=\left[\begin{array}{cccc}{\overline{a}}_{1,1}& {\overline{a}}_{1,2}& \cdots & {\overline{a}}_{1,|\mathbf{N}|}\\ {\overline{a}}_{2,1}& {\overline{a}}_{2,2}& \cdots & {\overline{a}}_{2,|\mathbf{N}|}\\ ⋮& ⋮& \ddots & ⋮\\ {\overline{a}}_{|\mathbf{N}|,1}& {\overline{a}}_{|\mathbf{N}|,2}& \cdots & {\overline{a}}_{|\mathbf{N}|,|\mathbf{N}|}\end{array}\right]\end{array}$$

   其中：

   $$\begin{array}{c}{\overline{a}}_{n,i}=\{\begin{array}{ll}{a}_{n,i}& ,\text{if}(i\in \text{pa}[n])\\ 0& ,\text{else}\end{array}\end{array}$$

   可以很容易的验证 $||\mathbf{A}|{|}_1=1$$||\mathbf A||_1 = 1$ 。

   马尔可夫理论认为：如果存在 $t$$t$ 使得矩阵 ${\mathbf{A}}^t$$\mathbf A^t$ 的所有元素都是非零的，则 $x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$x_n = \sum_{i\in \text{pa}[n]} a_{n,i}\times x_i$ 就是一个收缩映射。

   因此假设存在 $t$$t$ 使得矩阵 ${\mathbf{A}}^t$$\mathbf A^t$ 的所有元素都是非零的，则图上的随机游走是 GNN 的一个特例，其中 $F_{\mathbf{w}}(\cdot )$$F_{\mathbf w}(\cdot)$ 的参数 $\mathbf{A}$$\mathbf A$ 是一个常量随机矩阵（constant stochastic matrix），而不是由神经网络产生的矩阵。

   当输入图为无向图时，将 $\text{pa}[n]$$\text{pa}[n]$ 替换为邻域 $\text{ne}[n]$$\text{ne}[n]$，则结论仍然成立。

3. 读者注：GNN 的核心是不动点理论，通过节点的消息传播使得整张图的每个节点的状态收敛，然后在收敛的状态基础上预测。

   这里存在一个局限：基于不动点的收敛会导致节点之间的状态存在较多的消息共享，从而导致节点状态之间过于光滑（ over smooth ），这将使得节点之间缺少区分度。

   如下图所示，每个像素点和它的上下左右、以及斜上下左右八个像素点相邻。初始时刻蓝色没有信息量，绿色、黄色、红色各有一部分信息。

   • 开始时刻，不同像素点的区分非常明显。

   • 在不动点的收敛过程中，所有像素点都趋向于一致，最终整个系统的信息分布比较均匀。

   • 最终，虽然每个像素点都感知到了全局信息，但是我们已经无法根据每个像素点的最终状态来区分它们。

   

1.3 计算复杂度

1. 我们关心三种类型的 GNN 模型：positional GNN （其中 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 和 $g_{\mathbf{w}}(\cdot )$$g_{\mathbf w}(\cdot)$ 通过前馈神经网络来实现）、nonpositional linear GNN、nonpositional nonlinear GNN 。

   训练过程中一些复杂运算的计算复杂度见下表。为方便表述，我们假设训练集仅包含一张图。这种简化不影响结论，因为训练集所有的图总是可以合并为一张大图。另外，复杂度通过浮点运算量来衡量。

   具体推导见论文。其中：

   • instruction 表示具体的运算指令，positional/non-linear/linear 分别给出了三类 GNN 模型在对应运算指令的计算复杂度，execs 给出了迭代的次数。

   • $\text{hi}$$\text{hi}$ 表示隐层神经元的数量，即隐层维度。如 ${\text{hi}}_f$$\text{hi}_f$ 表示函数 $f_{\mathbf{w}}(\cdot )$$f_\mathbf w(\cdot)$ 的实现网络的隐层神经元数量。

   • ${\text{it}}_l$$\text{it}_l$ 表示迭代的 epoch 数量，${\text{it}}_b$$\text{it}_b$ 表示平均每个epoch 的反向迭代次数（BACKWARD 过程中的循环迭代次数），${\text{it}}_f$$\text{it}_f$ 表示平均每个epoch 的前向迭代次数（FORWARD 过程中的循环迭代次数）。

   • ${\overrightarrow{C}}_f$$\overrightarrow C_f$ 和 ${\overleftarrow{C}}_f$$\overleftarrow C_f$ 分别表示前向计算 $f_{\mathbf{w}}(\cdot )$$f_\mathbf w(\cdot)$ 和反向计算 $f_{\mathbf{w}}(\cdot )$$f_\mathbf w(\cdot)$ 梯度的计算复杂度。

   • 令雅克比矩阵 $\mathbf{A}=\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}$${\mathbf A}= \frac{\partial F_{\mathbf w}\left(\mathbf{\vec x},\vec l\right)}{\partial \mathbf{\vec x}}$ ，则罚项 $p_{\mathbf{w}}$$p_\mathbf w$ 为：

     $$p_{\mathbf{w}}=\sum _{j=1}^{s}L\left({\Vert {\mathbf{A}}^j\Vert }_1\right)=\sum _{u\in \mathbf{N}}\sum _{j=1}^{s}L(\sum _{(n,u)\in \mathbf{E}}\sum _{i=1}^s\left|{\mathbf{A}}_{i,j}^{n,u}\right|-\mu )=\sum _{u\in \mathbf{N}}\sum _{j=1}^s{\alpha }_{u,j}$$

     其中：${\mathbf{A}}_{i,j}^{n,u}$$\mathbf A^{n,u}_{i,j}$ 表示矩阵 $\mathbf{A}$$\mathbf A$ 的分块 ${\mathbf{A}}^{n,u}$$\mathbf A^{n,u}$ 的第 $i$$i$ 行第 $j$$j$ 列，${\mathbf{A}}^j$$\mathbf{ A}^j$ 表示矩阵 $\mathbf{A}$$\mathbf A$ 的第 $j$$j$ 列，${\alpha }_{u,j}=L(\sum _{(n,u)\in \mathbf{E}}\sum _{i=1}^s\left|{\mathbf{A}}_{i,j}^{n,u}\right|-\mu )$$\alpha_{u,j}=L\left(\sum_{(n,u)\in \mathbf E}\sum_{i=1}^s \left|\mathbf A_{i,j}^{n,u}\right|-\mu\right )$ 。

   • 定义 ${\mathbf{R}}^{n,u}$$\mathbf R^{n,u}$ 为一个矩阵，其元素为 ${\mathbf{R}}_{i,j}^{n,u}={\alpha }_{u,j}\times \text{sgn}\left({\mathbf{A}}_{i,j}^{n,u}\right)$$\mathbf R^{n,u}_{i,j} = \alpha_{u,j}\times \text{sgn}\left(\mathbf A^{n,u}_{i,j}\right)$ ，则 $t_{\mathbf{R}}$$t_\mathbf R$ 为：对所有的节点 $n$$n$ ，满足 ${\mathbf{R}}^{n,u}\ne \mathbf{0}$$\mathbf R^{n,u} \ne \mathbf 0$ 的节点 $u$$u$ 的数量的均值。通常它是一个很小的数值。

   

2. 当 GNN 模型训练完成之后，其推断速度也很快。

   • 对于positional GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{N}|{\overrightarrow{C}}_f)$$O(|\mathbf N|\overrightarrow C_g + \text{it}_f|\mathbf N|\overrightarrow C_f)$ 。

   • 对于 nonpositional nonliear GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{E}|{\overrightarrow{C}}_h)$$O(|\mathbf N|\overrightarrow C_g +\text{it}_f|\mathbf E|\overrightarrow C_h)$ 。

   • 对于 nonpositional linear GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{E}|s^2+|\mathbf{N}|{\overrightarrow{C}}_{\rho }+|\mathbf{E}|{\overrightarrow{C}}_{\varphi })$$O(|\mathbf N|\overrightarrow C_g+\text{it}_f|\mathbf E|s^2+|\mathbf N|\overrightarrow C_\rho+|\mathbf E|\overrightarrow C_\phi)$。

   推断阶段的主要时间消耗在计算状态 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的重复计算中，每次迭代的计算代价和输入图的维度（如边的数量）成线性关系，和前馈神经网络的隐层维度成线性关系，和状态向量的维度成线性关系。线性 GNN 是一个例外。线性 GNN 的单次迭代成本是状态维度的二次关系。

   状态向量的收敛速度取决于具体的问题。但是 Banach 定理可以确保它是以指数级速度收敛。实验表明：通常5 到 15 次迭代足以逼近不动点。

3. 在 positional GNN 中转移函数需要执行 ${\text{it}}_f|\mathbf{N}|$$\text{it}_f|\mathbf N|$ 次，在 nonpositional nonliear GNN 中转移函数需要执行 ${\text{it}}_f|\mathbf{E}|$$\text{it}_f|\mathbf E|$ 次。虽然边的数量 $|\mathbf{E}|$$|\mathbf E|$ 通常远大于节点数量 $|\mathbf{N}|$$|\mathbf N|$ ，但是positional GNN 和 nonpositional nonlinear GNN 的推断计算复杂度是相近的，这是因为 positional GNN 中的 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 网络通常要比 nonpositional nonliear GNN 中的 $h_{\mathbf{w}}(\cdot )$$h_{\mathbf w}(\cdot)$ 网络更复杂。

   • 在 positional GNN 中，实现 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的神经网络有 $M\times (s+d_E)$$M\times (s + d_E)$ 个神经元，其中 $M$$M$ 为所有节点的最大邻居数量。

   • 在 nonpositonal nonliear GNN 中，实现 $h_{\mathbf{w}}(\cdot )$$h_{\mathbf w}(\cdot)$ 的神经网络有 $(s+d_E)$$(s+d_E)$ 个神经元。

   只有在节点的邻居数量高度可变的图中才能注意到明显的差异，因为 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 的输入必须确保能够容纳最多的邻居，并且在应用 $f_{\mathbf{w}}(\cdot )$$f_{\mathbf w}(\cdot)$ 时许多输入可能仍然未使用（很多输入填充为 null ）。

4. 另一方面，观察到在 linear GNN 中，每次迭代仅使用一次 FNN，因此每次迭代的复杂度为 $O(s^2|\mathbf{E}|)$$O(s^2|\mathbf E|)$ 而不是 $O(|\mathbf{E}|{\overrightarrow{C}}_h)$$O(|\mathbf E|\overrightarrow C_h)$ 。

   注意到，当 $h_{\mathbf{w}}(\cdot )$$h_{\mathbf w}(\cdot)$ 由具有 ${\text{hi}}_h$$\text{hi}_h$ 隐层神经元的三层 FNN 实现时，${\overrightarrow{C}}_h=O((s+d_E+2d_N)\times {\text{hi}}_h)=O(s\times {\text{hi}}_h)$$\overrightarrow C_h = O((s+d_E+2d_N)\times \text{hi}_h) = O(s\times \text{hi}_h)$ 成立。在实际情况下，${\text{hi}}_h$$\text{hi}_h$ 通常大于 $s$$s$ ，因此线性模型比非线性模型更快。正如实验所证实的那样，这种优势通常被更差的效果所抵消。

5. GNN 的训练阶段要比推断阶段消耗更多时间，主要在于需要在多个epoch 中重复执行 forward 和 backward 过程。实验表明：forward 阶段和 backward 阶段的时间代价都差不多。

   • forward阶段的时间主要消耗在重复计算 $\overrightarrow{\mathbf{x}}(t)$$\mathbf{\vec x}(t)$。

   • 类似于 forward 阶段，backward 阶段的时间主要消耗在重复计算 $\overrightarrow{\mathbf{z}}(t)$$\mathbf{\vec z}(t)$ 。前述定理可以确保 $\overrightarrow{\mathbf{z}}(t)$$\mathbf{\vec z}(t)$ 是指数级收敛的，并且实验表明 ${\text{it}}_b$$\text{it}_b$ 通常很小。

6. 训练过程中，每个 epoch 的计算代价可以由上表中所有指令的计算复杂度的加权和得到，权重为指令对应的迭代次数。

   • 所有指令的计算复杂度基本上都是输入图的维度（如：边的数量）的线性函数，也是前馈神经网络隐单元维度的线性函数，也是状态维度 $s$$s$ 的线性函数。

     有几个例外，如计算 $\overrightarrow{\mathbf{z}}(t)={\mathbf{A}}^{\mathrm{\top }}\overrightarrow{\mathbf{z}}(t+1)+\overrightarrow{\mathbf{b}},\mathbf{A}=\frac{F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}},{\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$\mathbf{\vec z}(t) = \mathbf A^\top \mathbf{\vec z}(t+1) + \mathbf{\vec b}, \mathbf A = \frac{F_{\mathbf w}\left(\mathbf{\vec x},\vec l\right)}{\partial \mathbf{\vec x}}, \nabla_{\mathbf{w}}p_{\mathbf w}$ 的计算复杂度都是 $s$$s$ 的平方关系。

   • 最耗时的指令是 nonpositional nonlinear GNN 中计算 ${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$\nabla_{\mathbf{w}}p_{\mathbf w}$ ，其计算复杂度为 $t_{\mathbf{R}}\times max(s^2\times {\text{hi}}_h,{\overleftarrow{C}}_h)$$t_\mathbf R\times \max(s^2\times \text{hi}_h,\overleftarrow C_h)$ 。

     实验表明，通常 $t_{\mathbf{R}}$$t_\mathbf R$ 是一个很小的数字。在大多数 epoch 中 $t_{\mathbf{R}}=0$$t_\mathbf R=0$ ，因为雅可比矩阵 $\mathbf{A}$$\mathbf A$ 并未违反施加的约束。另一些情况中，$t_{\mathbf{R}}$$t_\mathbf R$ 通常在 1~5 之间。因此对于较小的状态维度 $s$$s$ ，计算 ${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$\nabla_{\mathbf{w}}p_{\mathbf w}$ 的复杂度较低。

     理论上，如果 $s$$s$ 非常大则可能导致 $s^2\times {\text{hi}}_h\gg {\overleftarrow{C}}_h$$s^2\times \text{hi}_h \gg \overleftarrow C_h$ 。如果同时还有 $t_{\mathbf{R}}\gg 0$$t_\mathbf R\gg 0$，则这将导致计算 ${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$\nabla_{\mathbf{w}}p_{\mathbf w}$ 非常慢。但是值得一提的是，我们的实验中从未观察到这种情况。